package org.example.struct.array;

import com.alibaba.fastjson.JSON;

import java.util.HashMap;
import java.util.Map;

/**
 * @author liyishan
 * @date 2023/7/17 14:23
 * @apiNote
 */

public class Test00001TwoSum {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4};
        int[] result = test4(a,5);
        System.out.println(JSON.toJSON(result));
    }

    private static int[] test1(int[] a, int target){
        int[] result =new int[2];
        ok:for(int i = 0;i<a.length;i++){
            for(int j = i;j<a.length;j++){
                if(a[i]+a[j] == target){
                    result[0] = i;
                    result[1] = j;
                    break ok;
                }
            }
        }
        return new int[0];
    }

    /**
     * 方法一：暴力破解
     * @param a
     * @param target
     * @return
     * 时间复杂度  O(N2)   空间复杂度 O(1)
     */
    private static int[] test2(int[] a, int target){
        for(int i = 0;i<a.length;i++){
            for(int j = i;j<a.length;j++){
                if(a[i]+a[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }


    private static int[] test3(int[] a, int target){
        int[] result =new int[2];
        for(int i = 0;i<a.length;i++){
            for(int j = i;j<a.length;j++){
                if(a[i]+a[j] == target){
                    result[0] = i;
                    result[1] = j;
                    break;
                }
            }
        }
        return new int[0];
    }

    /**
     * 方法二： hash表
     * @param a
     * @param target
     * @return
     * 时间复杂度  O(N)   空间复杂度  O(N)
     */
    private static int[] test4(int[] a,int target){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i= 0;i<a.length;i++){
            if(map.containsKey(target - a[i])){
                return new int[]{map.get(target - a[i]),i};
            }else{
                map.put(a[i],i);
            }
        }
        return new int[0];
    }




}
